HW#3 --- last modified January 01 1970 00:00:00..

Due date: Mar 21

Purpose: To learn about the relationship among various space and time complexity classes. To learn about the hierarchy theorem, reductions between classes, hardness and completeness.

Specification:

Do the following problems out of Papadimitriou: 7.4.3, 7.4.7, 7.4.8, 8.4.3, 9.5.2.

Point Breakdown